Date: Wed, 08 Jan 1997 20:50:03 GMT
Server: NCSA/1.4.2
Content-type: text/html

<!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
<!Converted with LaTeX2HTML 95 (Thu Jan 19 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds >
<HEAD>
<TITLE>The Halting Problem</TITLE>
</HEAD>
<BODY>
<meta name="description" value="The Halting Problem">
<meta name="keywords" value="handout4">
<meta name="resource-type" value="document">
<meta name="distribution" value="global">
<P>
 <BR> <HR><A NAME=tex2html1 HREF="node1.html"><IMG ALIGN=BOTTOM ALT="next" SRC="http://www.cs.washington.edu/general/latex2html_icons//next_motif.gif"></A>   <IMG ALIGN=BOTTOM ALT="up" SRC="http://www.cs.washington.edu/general/latex2html_icons//up_motif_gr.gif">   <IMG ALIGN=BOTTOM ALT="previous" SRC="http://www.cs.washington.edu/general/latex2html_icons//previous_motif_gr.gif">         <BR>
<B> Next:</B> <A NAME=tex2html2 HREF="node1.html">   About this document </A>
<BR> <HR> <P>
<P>
<H1>The Halting Problem</H1>
<P><STRONG></STRONG><P>
<P><STRONG></STRONG><P>
<P>
The halting problem is defined to be:
<UL><LI>
Input: Turing machine <b>M</b> and binary input <b>x</b>,
<LI>
Property: <b>M</b> halts on input <b>x</b>.
</UL>
<P>
<b> Theorem:</b> The halting problem is undecidable.
<P>
<b> Proof:</b>  The proof is by contradiction.  
Suppose that the halting problem is decidable.
Then there must be a Turing machine <b>H</b> with the
property that <b>H</b> halts on all inputs, and accepts <IMG  ALIGN=MIDDLE ALT="" SRC="img1.gif"> if and only if 
<b>M</b> halts on input <b>x</b>.
(Recall that <IMG  ALIGN=MIDDLE ALT="" SRC="img2.gif"> is the binary representation of the Turing machine <b>M</b>.)
<P>
We define a new Turing machine <b>D</b> which does the following on inputs of
the form <IMG  ALIGN=MIDDLE ALT="" SRC="img3.gif">.
<OL><LI>
Copy the input <IMG  ALIGN=MIDDLE ALT="" SRC="img4.gif"> to form the string <IMG  ALIGN=MIDDLE ALT="" SRC="img5.gif">.
<LI>
Run <b>H</b> on the input <IMG  ALIGN=MIDDLE ALT="" SRC="img6.gif">.
<OL><LI>
If <b>H</b> halts without accepting then <b>D</b> halts.
<LI>
If <b>H</b> halts and accepts then <b>D</b> simply loops forever.
</OL></OL>
<P>
There are two possibilities, <b>D</b> halts on input <IMG  ALIGN=MIDDLE ALT="" SRC="img7.gif"> or <b>D</b> does
not halt on input <IMG  ALIGN=MIDDLE ALT="" SRC="img8.gif">.
We will come to a contradiction in both cases.
<P>
If  <b>D</b> halts on input <IMG  ALIGN=MIDDLE ALT="" SRC="img9.gif">, then by the definition of <b>H</b>,
<b>H</b> accepts
<IMG  ALIGN=MIDDLE ALT="" SRC="img10.gif">.  By the definition of <b>D</b>, <b>D</b> does not halt on input <IMG  ALIGN=MIDDLE ALT="" SRC="img11.gif">.
<P>
If  <b>D</b> does not halt on input <IMG  ALIGN=MIDDLE ALT="" SRC="img12.gif">, then by the definition of <b>H</b>,
<b>H</b> halts on input <IMG  ALIGN=MIDDLE ALT="" SRC="img13.gif"> without accepting.  
By the definition of <b>D</b>, <b>D</b> halts on input <IMG  ALIGN=MIDDLE ALT="" SRC="img14.gif">.
<P>
<BR> <HR>
<UL> 
<LI> <A NAME=tex2html3 HREF="node1.html#SECTION00010000000000000000">   About this document ... </A>
</UL>
<BR> <HR>
<P><ADDRESS>
<I>James Fix <BR>
Tue Mar 12 11:18:16 PST 1996</I>
</ADDRESS>
</BODY>
